Polling a set of resources in a specific order and processing the first one found to have something to process is a common operation in networking and other fields. The order of polling can be defined by a priority list that orders the set of resources by some criteria. If the state of one of the resources changes, such as when the polling of queues discovers a packet in one of those queues that is then forwarded, the priority of that resource could change with respect to the other resources. Thus, after a polling round completes, the priority list may need to be reordered.
One networking application of this operation is a weighted fair queuing (WFQ) arbitrator that decides which queue of packets gets to send the next packet. Once a queue sends a packet, its priority is adjusted, the priority list is re-sorted and the re-sorted priority list is used in the next round. Thus, at most one queue changes its priority in each iteration. Even though a queue is the top priority, it may not have a packet to send, potentially requiring all the queues to be polled in priority order.
There are many ways to implement this operation. One naïve approach is to keep a priority for each queue in a dense array that we will call the priority queue, do a complete sort of the priority queue based on the relative weight of each queue after each iteration where relative weights may have changed and poll the queues in the priority order. The sort itself is expensive, requiring O(N log(N)) (where N is the number of queues) comparison/swap operations. In addition, such a sort is difficult to implement efficiently on processors with high branch penalties. Certain processors have high branch penalties, that is, they take more time to perform branches than other instructions. In such processors, it may actually save time to use more non-branch instructions rather than fewer branch instructions. Traditional sorting methods potentially require as many branches as comparisons, that is O(Nlg(N)) for a full sort and at least O(lg(N)) to do an insertion of a single element that has changed. Once the priority queue is sorted, it is traversed from highest priority to lowest priority, where each queue is polled in the order specified by the priority queue. The first queue that has a packet to send gets to send that packet and then has its weight appropriately adjusted. The process then repeats.
One implementation of this scheme has each element in the priority queue contain two values, a queue number and its relative weight. The priority queue is sorted on the relative weight and the queue number is moved along with the relative weight during the sort. Once the sort is complete, the priority queue contains a sorted list of queues and their relative weights, where the first element names the highest priority queue, the second element names the second highest priority queue and so on.
Another naïve queue polling approach uses a queue weight array instead of a priority queue. That queue weight array contains the relative weight for each of the queues, but not in sorted order. Thus, the first element contains the relative weight for queue 1, the second element contains the relative weight for queue 2 and so on. Using this queue weight array, one can scan the entire array looking for the highest priority queue. Once the highest priority queue is found, that queue is polled. If a packet is found, the packet is forwarded and the relative weight for the queue is adjusted. If a packet is not found in the highest priority queue, the queue weight array is scanned for the next highest priority queue and so on. This scheme is simple, but takes O(N2) operations to complete (N scans of N queues.) This approach is too slow for high performance applications.
There are many ways to implement this operation. One naïve approach to keep a priority for each queue in a dense array that we will call the priority queue, do a complete sort of the priority queue based on the relative weight of each queue after each iteration where relative weights may have changed and poll the queues in the priority order. The sort itself is expensive, requiring O(N log(N)) (where N is the number of queues) comparison/swap operations. In addition, such a sort is difficult to implement efficiently on processors with high branch penalties. Certain processors have high branch penalties; that is, they take more time to perform branches than other instructions. In such processors, it may actually save time to use more non-branch instructions rather than fewer branch instructions. Traditional sorting methods potentially require as many branches as comparisons, that is O(Nlg(N)) for a full sort and at least O(lg(N)) to do an insertion of a single element that has changed.
Once the priority order has been determined, the queues must be polled in the appropriate priority order. Jump tables are a time-efficient method to do polling. Rather than implement a loop that, using the priority list, successively determines the next queue to poll and polls that queue, a jump table implementation would jump to a piece of code that polls in the correct order without branching to determine the next thing to branch. For example, take a system with three queues that need to be polled in some priority order that periodically changes based on some criteria. There are only six possible priority orders to poll the queues: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. A jump table that encapsulated that knowledge might look like the following code:
Order_1_2_3:  Poll queue 1. If packet available forward and return  Poll queue 2. If packet available forward and return  Poll queue 3. If packet available forward and return  ReturnOrder_1_3_2:  Poll queue 1. If packet available forward and return  Poll queue 3. If packet available forward and return  Poll queue 2. If packet available forward and return  ReturnOrder_2_1_3:  Poll queue 2. If packet available forward and return  Poll queue 1. If packet available forward and return  Poll queue 3. If packet available forward and return  ReturnOrder_2_3_1:  Poll queue 2. If packet available forward and return  Poll queue 3. If packet available forward and return  Poll queue 1. If packet available forward and return  ReturnOrder_3_1_2:  Poll queue 3. If packet available forward and return  Poll queue 1. If packet available forward and return  Poll queue 2. If packet available forward and return  ReturnOrder_3_2_1:  Poll queue 3. If packet available forward and return  Poll queue 2. If packet available forward and return  Poll queue 1. If packet available forward and return  Return
Thus, at least one instance of every possible polling order is present in the jump table. In this case, there are six code strips, each encoding the necessary operations to perform one polling operation of a fixed queue priority order. Jump tables eliminate the control required by more traditional loop-based priority polling that would loop through each of the entries in the priority queue and would then require at least one conditional per loop iteration to branch back to the start of the loop. A jump table requires exactly one branch, that is, to the code strip that will execute the polls in the correct order. Of course, each poll requires a branch, but that is also true for a traditional loop-based scheme.
Jump tables applied to processing in priority order, however, have their inefficiencies as well. Assume that we have a sorted priority queue. How do we go from that queue to the appropriate jump table entry point?
Perhaps the simplest method is to compute an index from the sorted priority queue by using the queue numbers as digits in a base N number, where N is the number of queues. For example, in a three queue system, a priority queue might specify the priority order 2, 1, 3 (represented as 1, 0, 2 to be 0 offset). A unique index can be generated as follows:1N2+0N1+2N0 
Where N is 3, the number of queues. This method will generate a unique integer that will uniquely identify the priority order of the three queues. However, this method creates a number that is NN in range, and thus much larger than the N! required range to represent all possible permutations of N queues.
Thus, when using this technique to jump into a jump table, there is complexity in determining where to jump. Traditionally, a jump table is an array that is addressed with an integer. The addressed entry contains an address to jump to. If the integer range used to select a jump table entry point is contiguous and small, simple arithmetic operations or a simple lookup can be performed to generate the entry point address. In this case, since the integer range used is non-contiguous and large, the appropriate entry point cannot, in general, be simply computed from the integer; more complex operations such as a tree of branches are generally used instead.